#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

int T, n;
int rn, bn;
int a[200005];
ll q[200005];
ll dp[200005];
ll c, ans;
int main()
{
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1;i <= n; ++i)
            scanf("%d", a + i);
        if (n <= 17)
        {
            ans = -1;
            for (int i = 0;i < (1 << n); ++i)
            {
                c = 0, rn = bn = -1;
                //printf("i = %d\n", i);
                for (int j = 0;j < n; ++j)
                {
                    if (i >> j & 1)
                    {
                        if (rn == a[j + 1])
                            c += a[j + 1];
                        rn = a[j + 1];
                    }
                    else
                    {
                        if (bn == a[j + 1])
                            c += a[j + 1];
                        bn = a[j + 1];
                    }
                    //printf("%d %d\n", rn, bn);
                }
                ans = max(ans, c);
            }
            printf("%lld\n", ans);
        }
        else if (n <= 20005)
        {
            /*
            think:
            That's a great pity that the computer didn't offer us Chinese to write.
            As we set dp[i] that 1~i's answer, we can get:
            dp[i] = max{dp[j - 1] + d[j][i]}
            and:dp[i] = max{dp[j - 1] + d[j + 1][i - 1] + (a[i] == a[j] ? a[i] : 0)}
            d[j][i] means if you paint j to i same color, how much points will you get
            That can be yuchuli_ed by qianzhuihe.(is it?)
            I'll try this.
            OK now it's 17:56 and I found that it is fake
            but I'll keep it
            I wonder how much points will I get by this
            I think I'll get 0 points by the following program.
            But I still want to say that it is so generous to give us 20 pts for free!
            */
            memset(q, 0, sizeof(q));
            memset(dp, 0, sizeof (dp));
            for (int i = 1;i <= n; ++i)
            {
                q[i] = q[i - 1];
                if (a[i] == a[i - 1])
                    q[i] += a[i];
            }
            for (int i = 1;i <= n; ++i)
            {
                for (int j = 1;j < i; ++j)
                {
                    ll v;
                    if ((i - j) % 2 == 1)//i ~ j + 1
                        v = q[i] - q[j + 1];
                    else
                        v = q[i] - q[j];
                    dp[i] = max(dp[i], dp[j] + v);
                    //another choice
                    if (j != i - 1)
                    {
                        if ((i - 1 - j) % 2 == 1)//i - 1 ~ j + 1
                            v = q[i - 1] - q[j + 1];
                        else
                            v = q[i - 1] - q[j];
                        dp[i] = max(dp[i], dp[j - 1] + v + (a[i] == a[j] ? a[i] : 0));
                    }
                }
                //printf("%lld\n", dp[i]);
            }
            printf("%lld\n", dp[n]);
        }
        else
        {
            printf("0\n");
        }
    }
    return 0;
}
